package org.thewares.collection;
case class ReverseDeque[+A](inner:Deque[A]) extends Deque[A] {
      def apply(i:Int):A=inner.apply(length-i-1);
      def elements: Iterator[A]=inner.reverseElements;
      def reverseElements: Iterator[A]=inner.elements;

      override def isEmpty: Boolean=inner.isEmpty;
      def length:Int=inner.length;

      def reverseDeque=inner;

      def ++[B >: A](s:Seq[B]):Deque[B]=s match {
	    case d:Deque[B] if d.length>length => this ::: d;
	    case _ => {
		  val i:Deque[B]=inner;
		  ReverseDeque((i /: s){(d,e) => e :: d});
	    }
      }

      def :::[B >: A](that:Deque[B]):Deque[B]= {
	    if (that.length>length){
		  that ++ this;
	    } else {
		  val i:Deque[B]=inner;
		  ReverseDeque((i /: that){(d,e) => e :: d});
	    }
      }


      /** Creates a new deque with element added at the end
       *  of the old deque.  This is the same as push
       *
       *  @param  elem        the element to insert
       */
      def enqueue[B >: A](elem: B):Deque[B]=ReverseDeque(elem::inner);

      /** Creates a new deque with element added at the end
       *  of the old deque.  This is the same as push.
       *
       *  @param  elem        the element to insert
       */
      def +[B >: A](elem: B):Deque[B]=ReverseDeque(elem::inner);

      /** Creates a new deque with element added at the end
       *  of the old deque.
       *
       *  @param  elem        the element to insert
       */
      def push[B >: A](elem: B):Deque[B]=ReverseDeque(elem::inner);

      def peek:A=inner.head;


      /** Returns a new Deque with the last element in the deque removed
       *
       *  @throws Predef.NoSuchElementException
       *  @return a new Deque
       */
      def pop:Deque[A]=ReverseDeque(inner.tail);

      /** Returns a tuple with the last element in the deque,
       *  and a new deque with this element removed.
       *
       *  This is the same as (peek,pop);
       *
       *  @throws Predef.NoSuchElementException
       *  @return a tuple with the last element of the deque
       *  and the rest of the Deque
       */
      def peekPop: (A, Deque[A])= (peek,pop);


      /** Creates a new deque with element added at the front
       *  of the old deque.
       *
       *  @param  elem        the element to insert
       */
      def unshift[B >: A](elem: B):Deque[B] = ReverseDeque(inner+elem);

      /** Creates a new deque with element added at the front
       *  of the old deque. Same as unshift.
       *
       *  @param  elem        the element to insert
       */
      def ::[B >: A](elem: B):Deque[B] = ReverseDeque(inner+elem);
      
      /** Returns a new Deque with the last element in the deque removed
       *
       *  this is the same as tail
       *
       *  @throws Predef.NoSuchElementException
       *  @return a new Deque
       */     
      def shift: Deque[A] = ReverseDeque(inner.pop);

      /** Returns a tuple with the first element and a new Deque with the other elements
       *
       * this is the same as (head,tail)
       *
       *  @throws Predef.NoSuchElementException
       */     
      // This is what s.c.i.Queue does.
      def dequeue: (A, Deque[A])= (head,tail);
      
      /** Returns the first element
       *
       *  @throws Predef.NoSuchElementException
       *  @return the first element 
       */     
      
      def head: A=inner.peek;

      /** Returns a Deque with all the elements except the first
       *
       *  @throws Predef.NoSuchElementException
       *  @return a new Deque
       */     
      def tail: Deque[A]=ReverseDeque(inner.pop);

      def nodes:Int=inner.nodes;
      def depth:Int=inner.depth+1;
      def state:String="R("+inner.state+")";

}
